#include<iostream>
#include <algorithm>  
using namespace std;
/// @brief 定义二叉树节点Node的基类
/// @tparam Comparable 
template <typename Comparable>
class Node
{
    /// @brief Node节点的成员，不需要也不能更改
    /// @tparam Comparable 
    private:
        ///@brief 节点中的元素值
        Comparable element;
        ///@brief 左子树
        Node *left;
        /// @brief 右子树
        Node *right;

    /// @brief Node节点的成员函数，被继承的时候可以根据实际类的需求进行更改
    /// @tparam Comparable 
    public:
        /// @brief 定义构造函数(左值、右值引用)，并且构造函数不能是虚函数！！！
        /// @brief 而且，在构造函数中调用虚函数，实际执行的是父类的对应函数，
        /// @brief 自己还没有构造好, 多态是被disable的
        /// @tparam Comparable 
        Node(const Comparable & element,Node *lt,Node *rt )
            :element{element},left{lt},right{rt} { }
        
        Node(const Comparable &&element,Node *lt,Node *rt)
            :element{ std::move( element ) }, left{ lt }, right{ rt } { }

        /// @brief 定义纯虚的析构函数!!!这是复杂类结构所必须的
        virtual ~Node();

}



/**
 * @brief 设计二叉树基类，并添加以下成员
 * BinarySearchTree class
 *
 * CONSTRUCTION: zero parameter
 *
 * ******************PUBLIC OPERATIONS*********************
 * void insert( x )       --> Insert x
 * void remove( x )       --> Remove x
 * bool contains( x )     --> Return true if x is present
 * Comparable findMin( )  --> Return smallest item
 * Comparable findMax( )  --> Return largest item
 * boolean isEmpty( )     --> Return true if empty; else false
 * void makeEmpty( )      --> Remove all items
 * void printTree( )      --> Print tree in sorted order
 * ******************ERRORS********************************
 * Throws UnderflowException as warranted

 * @tparam Comparable 
 */
template <typename Comparable>
class BinaryTree
{  
    /// @brief 对二叉树来说，除了Node成员以外，还需要有一个root，但在基类中可以无须实现,在子类中进行声明
    /// @tparam Comparable 
    //private:
        //Node * root;
    
    public:
        /// @brief 定义构造函数，并且构造函数不能是虚函数！！！
        /// @brief 而且，在构造函数中调用虚函数，实际执行的是父类的对应函数，
        /// @brief 自己还没有构造好, 多态是被disable的
        BinaryTree()
        {

        };
        /// @brief 定义纯虚的析构函数!!!
        virtual ~BinaryTree()
        {

        }

        /// @brief 拷贝赋值，左值
        /// @param rhs 
        /// @return 赋值后的BinaryTree;
        virtual BinaryTree & operator=( const BinaryTree & rhs )
        {

        }

        /// @brief 拷贝赋值，右值
        /// @param rhs 
        /// @return 赋值后的BinaryTree;
        virtual BinaryTree & operator=( BinaryTree && rhs )
        {

        }

        /// @brief 找最小值，如果寻找不合法，抛出异常
        /// @tparam Comparable 
        virtual const Comparable & findMin() const

        /// @brief 找最大值，如果寻找不合法，抛出异常
        /// @return 
        virtual const Comparable & findMax( ) const
        {

        }

        /// @brief 查找二叉树中是否含有x这个值
        /// @param x 
        /// @return 含有x的话，返回真；否则返回假
        virtual bool contains( const Comparable & x ) const
        {
            
        }

        /// @brief 判断二叉树是否为空
        /// @return 不为空的话，返回假；否则返回真
        virtual bool isEmpty( ) const
        {
            
        }

        /// @brief 打印树的节点
        virtual void printTree( ) const
        {

        }

        /// @brief 清空树，并释放内存
        virtual void makeEmpty( )
        {

        }

        /// @brief 左值插入x
        /// @param x 
        virtual void insert( const Comparable & x )
        {
            
        }
        
        /// @brief 右值插入x
        /// @param x 
        virtual void insert( Comparable && x )
        {

        }
        
        /// @brief 删除树中element==x的节点
        /// @param x 
        virtual void remove( const Comparable & x )
        {

        }
}

/// @brief 实现子类::二叉搜索树
/// @tparam Comparable 
template <typename Comparable>
class BinarySearchTree:public BinaryTree<Comparable>
{
    private:
        /// @brief BinarySearchNode模板类，继承了Node基类;
        class BinarySearchNode:public Node<Comparable>
        {

        }
        /// @brief 对二叉树来说，除了Node成员以外，还需要有一个root，但在基类中可以无须实现,在子类中进行声明
        BinarySearchNode* root;
    public:
        /// @brief 构造函数需要对root初始化
        BinarySearchTree():root{nullptr}
        {

        }

        /**
         * @brief 二叉搜索树的特殊之处在于插入、删除时候会根据节点大小进行排序，这里需要修改，重新实现
         * 
         * @param x 
         */

        /// @brief 左值插入x
        /// @param x 
        virtual void insert( const Comparable & x )
        {
            
        }
        /// @brief 右值插入x
        /// @param x 
        virtual void insert( Comparable && x )
        {

        }
        /// @brief 删除树中element==x的节点
        /// @param x 
        virtual void remove( const Comparable & x )
        {

        }
}


/// @brief 实现子类::二叉平衡树
/// @tparam Comparable 
template <typename Comparable>
class AvlTree:public BinaryTree<Comparable>
{
    private:
        /// @brief AvlNode模板类，继承了Node基类;
        class AvlNode:public Node<Comparable>
        {
            private:
                int height;
            public:
               Node(const Comparable & element,Node *lt,Node *rt,const int & h )
                    :element{element},left{lt},right{rt},height{h} { }
        
               Node(const Comparable &&element,Node *lt,Node *rt,const int && h)
                   :element{ std::move( element ) }, left{ lt }, right{ rt },height{std::move(h)} { }

        }
        /// @brief 对二叉树来说，除了Node成员以外，还需要有一个root，但在基类中可以无须实现,在子类中进行声明
        AvlNode* root;
    public:
        /// @brief 构造函数需要对root初始化
        AvlTree():root{nullptr}
        {

        }

        /**
         * @brief 平衡树的特殊之处在于插入、删除时候会根据节点大小进行排序，
         * @brief 并且保证叶子节点的height之差<=1，这里需要修改，重新实现
         * @param x 
         */

        /// @brief 左值插入x
        /// @param x 
        virtual void insert( const Comparable & x )
        {
            
        }
        /// @brief 右值插入x
        /// @param x 
        virtual void insert( Comparable && x )
        {

        }
        /// @brief 删除树中element==x的节点
        /// @param x 
        virtual void remove( const Comparable & x )
        {

        }
        /// @brief 平衡二叉树，保证叶子节点的高度差不大于1；否则进行调整
        virtual void balance(const AvlNode* &t)
        {

        }
}


/// @brief 实现子类::二叉splay树
/// @tparam Comparable 
template <typename Comparable>
class SplayTree:public BinaryTree<Comparable>
{
    private:
        /// @brief SplayNode模板类，继承了Node基类;
        class SplayNode:public Node<Comparable>
        {

        }
        /// @brief 对二叉树来说，除了Node成员以外，还需要有一个root，但在基类中可以无须实现,在子类中进行声明
        SplayNode* root;
    public:
        /// @brief 构造函数需要对root初始化
        SplayTree():root{nullptr}
        {

        }

        /**
         * @brief splay树的特殊之处在于插入、删除时候会根据节点大小进行排序，
         * @brief 并且保证访问一个节点的时候，进行旋转操作使得其向root更加靠近
         * @param x 
         */

        /// @brief 左值插入x
        /// @param x 
        virtual void insert( const Comparable & x )
        {
            
        }
        /// @brief 右值插入x
        /// @param x 
        virtual void insert( Comparable && x )
        {

        }
        /// @brief 删除树中element==x的节点
        /// @param x 
        virtual void remove( const Comparable & x )
        {

        }
        /// @brief 并且保证访问一个节点的时候，进行旋转操作使得其向root更加靠近
        virtual void balance(const AvlNode* &t)
        {

        }
}


